#include<bits/stdc++.h>
using namespace std;

int n,k;
string tost(int i,string& s){
    string res="";
    int p=0;
    int l=-30;
    while(i){
        if(i&1){
            if(p-l>k){
                res=res+s[p];
                l=p;
            }
            else{
                return "-1";
            }
        }
        i>>=1;
        p++;
    }
    return res;
}

void solve(){
    cin>>n>>k;
    string s;
    cin>>s;
    set<string> st;
    for(int i=1;i<pow(2,n);i++){
        string temp=tost(i,s);
        if(temp=="-1")continue;
        st.insert(temp);
    }
    cout<<st.size()<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
    return 0;
}